package _03LinkedList;

class _04DeleteSinglyLinkedList {
    // Singly linked list node in Java
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    Node head;
    // time complexity： O(1)
    // space complexity: O(1)
    // inserts a new node on the front of the list.
    public void push(int data) {
        // allocate new node
        Node newNode = new Node(data);

        // insert
        newNode.next = head;
        head = newNode;
    }

    // time complexity： O(n)
    // space complexity: O(1)
    // delete key node in linked list
    // TODO: add head
    void deleteNode(int key) {

        Node prev = null;
        Node temp = head;

        // head is null
        if(head == null) return;

        // head's data is key
        if(head.data == key)
            head = head.next;
        else{
            // while store prev
            while(temp != null && temp.data != key) {
                prev = temp;
                temp = temp.next;
            }
            // not found
            if(temp == null)
                return;
            // new link
            prev.next = temp.next;
            return;
        }
        return;
    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        _04DeleteSinglyLinkedList list = new _04DeleteSinglyLinkedList();

        list.push(3);
        list.push(9);
        list.push(5);
        list.push(8);
        list.push(2);
        System.out.print("Linked List: ");
        list.printList();
        System.out.println();

        list.deleteNode(111);
        System.out.print("after delete Linked List: ");
        list.printList();

    }
}

